// 动态规划（Dynamic Programming，DP）是一种将复杂问题分解成更小的子问题来解决的优化技术。

// 用动态规划解决问题时，要遵循三个重要步骤：
// (1) 定义子问题
// (2) 实现要反复执行来解决子问题的部分
// (3) 识别并求解出边界条件


// --------------------- 最少硬币找零问题 ------------------------

class MinCoinChange {
  constructor(coins) {
    // 接收的数组
    this.coins = coins;
    this.cache = {};
  }

  makeChange(amount) {
    if (!amount) {
      return [];
    }

    if (this.cache[amount]) {
      return this.cache[amount];
    }

    let min = [];
    let newMin, newAmount;
    for (let i = 0; i < this.coins.length; i++) {
      const coin = this.coins[i];
      newAmount = amount - coin;
      if (newAmount >= 0) {
        newMin = this.makeChange(newAmount);
      }

      if (
          newAmount >= 0 && 
          (newMin.length < min.length -1 || !min.length) &&
          (newMin.length || !newAmount)
          ) {
          min = [coin].concat(newMin);
          console.log('new Min ' + min + ' for ' + amount); 
      }
    }

    return (this.cache[amount] = min)
  }
}

const minCoin = new MinCoinChange([1, 3, 4]);

minCoin.makeChange(6);


